/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root)  return vector<vector<int>>((0,0));
        /*
        “之”字型打印符合栈“先进后出”的特性；考虑到本题实际，需要用到两个栈交叉存储各层节点；
        在奇数层时，将子节点存入stEven中，顺序是先左节点后右结点；
        在偶数层时，将子节点存入stOdd中，顺序是先右节点后左结点
        */
        vector<vector<int>> result;
        stack<TreeNode*> stEven;  //存储偶数层节点
        stack<TreeNode*> stOdd;  //存储奇数层节点
        stOdd.push(root);

        while(!stOdd.empty() || !stEven.empty()){
            vector<int> resultTemp;  //存储该层的打印结果
            if(stEven.empty()){
                while(!stOdd.empty()){
                    resultTemp.push_back(stOdd.top()->val);
                    if(stOdd.top()->left)  stEven.push(stOdd.top()->left);
                    if(stOdd.top()->right)  stEven.push(stOdd.top()->right);
                    stOdd.pop();
                }
            }else{
                while(!stEven.empty()){
                    resultTemp.push_back(stEven.top()->val);
                    if(stEven.top()->right)  stOdd.push(stEven.top()->right);
                    if(stEven.top()->left)  stOdd.push(stEven.top()->left);
                    stEven.pop();
                }
            }
            result.push_back(resultTemp);
        }

        return result;
    }
};